package questions.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import datastructure.list.ListNode;
import datastructure.tree.TreeNode;

/**
 * 
 * class: questions.LeetcodeTree
 * @author wxu
 * @since Sep 2, 2014
 */
public class LeetcodeTree {
	
	/**
	 * Same Tree
	 * https://oj.leetcode.com/problems/same-tree/
	 */
	public boolean isSameTree(TreeNode p, TreeNode q) {
		if(p == null && q == null) return true;
		else if ( p != null && q != null && p.val != q.val ) return false;
		else if ( p == null || q == null) return false;
		
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
	

	
	/**
	 * https://oj.leetcode.com/problems/symmetric-tree/
	 * Symmetric Tree
	 * @param root
	 * @return
	 */
	public boolean isSymmetricTree(TreeNode root) {
		_log.append("iterate:" + isSymmetric(root));
        return isSymmetric(root.left, root.right);
    }
	
	// recursively
	private boolean isSymmetric(TreeNode left, TreeNode right){
		if( left == null && right == null) return true;
		else if ( left != null && right != null && left.val != right.val) return false;
		else if( left == null || right == null) return false;
		
		return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
	}
	
	private boolean isSymmetric(TreeNode root){
		TreeNode[] current = new TreeNode[2];
		
		current[0]=root.left;
		current[1] = root.right;
		boolean endOfTree = false;
		while(!endOfTree){
			TreeNode[] next = new TreeNode[current.length * 2];
			endOfTree = true;
			for( int i = 0;i< current.length /2 ; i ++){
				TreeNode left = current[i];
				TreeNode right = current[current.length - i - 1];
				
				if( left == null && right == null) continue;
				else if( left != null && right != null && left.val != right.val) return false;
				else if ( left == null || right == null) return false;
				
				next[2 * i] = left.left;
				next[2*i + 1] = right.right;
				
				next[2 * (current.length - i - 1)] = right.left;
				next[2 * (current.length - i - 1) + 1] = right.right;
				
				endOfTree = false;
			}
			
			current = next;
		}
		
		return true;
	}
	
	/**Construct Binary Tree from Inorder and Postorder Traversal 
	 * https://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
	 * @param inorder
	 * @param postorder
	 * @return
	 */
public TreeNode buildTree(int[] inorder, int[] postorder) {
        return null;
    }
	
	/**
	 * https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/
	 * Binary Tree Level Order Traversal II
	 * @param root
	 * @return
	 */
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		List<TreeNode> list = new ArrayList<TreeNode>();
		List<TreeNode> next = new ArrayList<TreeNode>();
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		List<Integer> values = new ArrayList<Integer>();
		
		list.add(root);
		while(!list.isEmpty()){
			for( int i = 0;i<list.size() ; i++){
				TreeNode temp = list.get(i);
				values.add(temp.val);
				if(temp.left != null) next.add(temp.left);
				
				if(temp.right != null) next.add(temp.right);
			}
			result.add(values);
			
			list = next;
			next = new ArrayList<TreeNode>();
			values = new ArrayList<Integer>();
		}
	
		Collections.reverse(result);
		
		return result;
    }
	
	/**
	 * https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
	 * Convert Sorted List to Binary Search Tree
	 * @param head
	 * @return
	 */
	public TreeNode sortedListToBST(ListNode head) {
        List<ListNode> list = new ArrayList<ListNode>();
        
        do{
        	list.add(head);
        	head = head.next;
        }while( head != null);
        
		return listToBST(list, 0, list.size());
    }
	
	private TreeNode listToBST(List<ListNode> list, int from, int to){
		if(from > to) return null;
		
		int mid = from + (to - from)/2;
		TreeNode result = new TreeNode(list.get(mid).val);
		
		result.left = listToBST(list, from, mid);
		result.right = listToBST(list, mid + 1, to);
		
		return result;
	}
	
	/**
	 * Binary Tree Preorder Traversal 
	 * https://oj.leetcode.com/problems/binary-tree-preorder-traversal/
	 */
	public List<Integer> preorderTraversal(TreeNode root) {
        return null;
    }
	
	/**
	 * https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
	 * Binary Tree Postorder Traversal 
	 * @param root
	 * @return
	 */
	public List<Integer> postorderTraversal(TreeNode root) {
        return null;
    }
	
	/**
	 * https://oj.leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
	 * Convert Sorted Array to Binary Search Tree
	 * @param num
	 * @return
	 */
	public TreeNode sortedArrayToBST(int[] num) {
        return arraytoBST(num, 0, num.length);
    }
	
	private TreeNode arraytoBST(int[] num, int from, int to){
		if( from > to) return null;
		
		int mid = from + (to -from)/2;
		TreeNode result = new TreeNode(num[mid]);
		
		result.left = arraytoBST(num, from, mid);
		result.right = arraytoBST(num, mid+ 1, to);
		
		return result;
	}
	
	
	/**
	 * https://oj.leetcode.com/problems/balanced-binary-tree/
	 * Balanced Binary Tree
	 * @param root
	 * @return
	 */
	public boolean isBalanced(TreeNode root) {
        
		return maxDepth(root) - minDepth(root) <=1;
    }
	
	private int maxDepth( TreeNode root){
		if( root == null) return 0;
		
		return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
	}
	
	/**
	 * https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
	 * Minimum Depth of Binary Tree 
	 * @param root
	 * @return
	 */
	public int minDepth(TreeNode root) {
		if( root == null) return 0;
		
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
	
	/**
	 * Flatten Binary Tree to Linked List
	 * https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
	 * @param root
	 */
	public void flatten(TreeNode root) {
        flattenR(root);
    }
	
	private TreeNode[] flattenR(TreeNode node){
		if(node.left == null && node.right == null) return new TreeNode[]{node, node};
		
		TreeNode[] result = null;
		if( node.left != null){
			result = flattenR(node.left);
		}
		
		if(node.right != null){
			TreeNode[] rightList = flattenR(node.right);
			if( result != null){
				result[1].right = rightList[0];
				result[1] = rightList[1];
			}else{
				result = rightList;
			}
		}
		
		node.left = null;
		node.right = result[0];
		
		return new TreeNode[]{node, result[1]};
	}
	
	/**
	 * https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/
	 * Sum Root to Leaf Numbers 
	 * @param root
	 * @return
	 */
	public int sumNumbers(TreeNode root) {
        
		
		return sumNumbers(root, 0);
    }
	
	private int sumNumbers(TreeNode node, int sum){
		sum = sum * 10 + node.val;
		
		if( node.left == null && node.right == null) return sum;
		
		int result = 0;
		if(node.left != null){
			result = sumNumbers( node.left, sum);
		}
		
		if( node.right != null){
			result += sumNumbers(node.right, sum);
		}
		
		return result;
	}
	
	
	
	
	
	
////////////////////////////////////////////////////////////////////////////////////////////////	
	
	private final  StringBuilder _log= new StringBuilder();
	
	public  String getLog(){
		return _log.toString();
	}

}
